Search results for "Random binary tree"
showing 5 items of 5 documents
A distance metric on binary trees using lattice-theoretic measures
1990
A so called height function which is a strictly antitone supervaluation is defined on binary trees. Via lattice-theoretic results and using the height function, we can define a distance metric on binary trees of size n which can be computed in expected time O(n 3/2 )
On the listing and random generation of hybrid binary trees
1994
We consider in this paper binary trees whose internal nodes are either associative or non-associative. Hybrid binary trees are equivalence classes with respect to the associative property. We count, list and generate randomly hybrid binary trees using Fibonacci numbers.
Generation of Valid Labeled Binary Trees
2003
International audience; Generating binary trees is a well-known problem. In this paper, we add some constraints to leaves of these trees. Such trees are used in the morphing of polygons, where a polygon P is represented by a binary tree T and each angle of P is a weight on a leaf of T. In the following, we give two algorithms to generate all binary trees, without repetitions, having the same weight distribution to their leaves and representing all parallel polygons to P.
Right-arm rotation distance between binary trees
2003
We consider a transformation on binary trees, named right-arm rotation, which is a special instance of the well-known rotation transformation. Only rotations at nodes of the right arm of the trees are allowed. Using ordinal tools, we give an efficient algorithm for computing the right-arm rotation distance between two binary trees, i.e., the minimum number of rightarm rotations necessary to transform one tree into the other.